#include<bits/stdc++.h>

using namespace std;
int n,m,p,jc;
struct daduoli
{
	int b,xb;
}b[8010];
int a[8010],xa[8010];
int x,y,z;
bool cmp(daduoli a,daduoli b)
{
	if(a.b!=b.b) return a.b<b.b;
	else return a.xb<b.xb;
}
int main()
{
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		b[i].xb=i;
		b[i].b=a[i];
	}
	sort(b+1,b+1+n,cmp);
	for(int i=1;i<=n;++i)
	{
		xa[b[i].xb]=i;
	}
	b[n+1].b=2100000000;
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		if(x==1)
		{
			scanf("%d",&z);
			if(a[y]==z)continue;
			if(z<a[y])
			{
				a[y]=z;
				int r=xa[y];
				for(int j=r-1;j>=0;--j)
				{
					if(b[j].b<z)
					{
						p=j+1;
						break;
					}
					if(b[j].b==z&&b[j].xb<y)
					{
						p=j+1;
						break;
					}
				}
				b[r].b=z;
				for(int j=r;j>=p+1;--j)
				{
					xa[b[j].xb]=j-1;
					xa[b[j-1].xb]=j;
					swap(b[j].b,b[j-1].b);
					swap(b[j].xb,b[j-1].xb);
				}
			}
			if(z>a[y])
			{
				a[y]=z;
				int r=xa[y];
				for(int j=r+1;j<=n+1;++j)
				{
					if(b[j].b>z)
					{
						p=j-1;
						break;
					}
					if(b[j].b==z&&b[j].xb>y)
					{
						p=j-1;
						break;
					}
				}
				b[r].b=z;
				for(int j=r;j<=p-1;++j)
				{
					xa[b[j].xb]=j+1;
					xa[b[j+1].xb]=j;
					swap(b[j].b,b[j+1].b);
					swap(b[j].xb,b[j+1].xb);
				}
			}
			continue;
		}
		printf("%d\n",xa[y]);
	}
	return 0;
}
